#include "stdafx.h"
#include "CMatrixChainMultiply.h"
#include "include/tool.h"
#include <gtest/gtest.h>

void MatrixChainOrder(int p[], int size, int m[], int s[]) {
    int n = size-1;
    for (int i = 1; i <= n; ++i) {
        m[i*n+i] = 0;
    }
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i <= n-l+1; ++i) {
            int j = i+l-1;
            m[i*n+j] = std::numeric_limits<int>::max();
            for (int k = i; k <= j-1; ++k) {
                int q = m[i*n+k] + m[(k+1)*n+j] + p[i-1]*p[k]*p[j];
                if (q < m[i*n+j]) {
                    m[i*n+j] = q;
                    s[i*n+j] = k;
                }
            }
        }
    }
}

int MatrixChain(int p[], int size, int i, int j, int m[], int s[]) {
    if (i == j) {
        m[i*(size-1)+j] = 0;
        return m[i*(size-1)+j];
    } else {
        int min = std::numeric_limits<int>::max();
        int kk = std::numeric_limits<int>::max();
        for (int k = i; k < j; ++k) {
            int q = MatrixChain(p, size, i, k, m, s) + MatrixChain(p, size, k+1, j, m, s) + p[i-1]*p[k]*p[j];
            if (q < min) {
                min = q;
                kk = k;
            }
        }
        m[i*(size-1)+j] = min;
        s[i*(size-1)+j] = kk;
        return min;
    }
}

void PrintOptimalParens(int s[], int size, int i, int j) {
    if (i == j) {
        std::cout << "A" << i;
    } else {
        std::cout << " (";
        PrintOptimalParens(s, size, i, s[i*size+j]);
        PrintOptimalParens(s, size, s[i*size+j]+1, j);
        std::cout << ") ";
    }
}

CMatrixChainMultiply::CMatrixChainMultiply()
{
    //ctor
}

CMatrixChainMultiply::~CMatrixChainMultiply()
{
    //dtor
}

int CMatrixChainMultiply::run(void) {
    /*
    //int p[] = {5, 10, 3, 12, 5, 50, 6};
    int p[] = {30, 35, 15, 5, 10, 20, 25};
    {
        std::cout << "a tabular, bottom-up approach matrix chain :" << std::endl;
        int length = SIZE(p);
        int n =  SIZE(p)-1;
        int *m = new int[(n+1)*(n+1)];
        int *s = new int[(n+1)*(n+1)];
        MatrixChainOrder(p, length+1, m, s);
        PrintOptimalParens(s, n+1, 1, n);
        delete [] m;
        delete [] s;
        std::cout << std::endl;
    }
    {
        std::cout << "a recursive algorithm of matrix chain :" << std::endl;
        int length = SIZE(p);
        int n =  SIZE(p)-1;
        int *m = new int[(n+1)*(n+1)];
        int *s = new int[(n+1)*(n+1)];
        MatrixChain(p, length+1, 1, n+1, m, s);
        PrintOptimalParens(s, n+1, 1, n);
        delete [] m;
        delete [] s;
        std::cout << std::endl;
    }
    */
    return 0;
}

TEST(CMatrixChainMultiply, run)
{
	CMatrixChainMultiply().run();
}